class Solution {
    public int max = 0;
    public boolean visited[][];
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        dfs(m,n,k,0,0,0);
        return max;
    }
      // 计算两个坐标数字的和
    private int sumfun(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
    public void dfs(int m, int n,int k,int i,int j,int retMax) {
        int sum = 0;
        sum = sumfun(i,j);
        if(i<0 || j<0 || i>m-1 || j>n-1 || sum>k || visited[i][j]) {
            return;
        }
        max++;
        //记录这个格子被访问过
        visited[i][j] = true;
        dfs(m,n,k,i-1,j,retMax);
        dfs(m,n,k,i+1,j,retMax);
        dfs(m,n,k,i,j+1,retMax); 
        dfs(m,n,k,i,j-1,retMax);
    }

   
}